import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import static org.junit.Assert.assertTrue;

public class Subset {

	public static void main(String[] args) {
		Set<Integer> set = new HashSet<Integer>();
		set.add(1);
		set.add(2);
		set.add(3);
		//set.add(4);
		//set.add(5);

		Subset s = new Subset();
		
		System.out.println("Non recursive");
		Set<Set<Integer>> subsets2 = s.getSubsetNonRecursive(set);
		for (Set<Integer> subset : subsets2) {
			System.out.println(subset.toString());
		}
		
		System.out.println("Recursive");
		Set<Set<Integer>> subsets = s.getSubset(set);

		for (Set<Integer> subset : subsets) {
			System.out.println(subset.toString());
		}	
		
		assertTrue(subsets2.size() == subsets.size());
	}

	public Set<Set<Integer>> getSubset(Set<Integer> set) {
		if (set == null || set.isEmpty()) {
			Set<Set<Integer>> subsets = new HashSet<Set<Integer>>(1);
			subsets.add(new HashSet<Integer>());
			return subsets;
		}

		Iterator<Integer> iter = set.iterator();
		Integer elem = iter.next();

		set.remove(elem);
		Set<Set<Integer>> subsets = getSubset(set);
		Set<Set<Integer>> newSubsets = new HashSet<Set<Integer>>(subsets.size());
		for (Set<Integer> subset : subsets) {
			Set<Integer> newSubset = new HashSet<Integer>(subset);
			newSubset.add(elem);
			newSubsets.add(newSubset);
		}

		subsets.addAll(newSubsets);
		return subsets;
	}
	
	public Set<Set<Integer>> getSubsetNonRecursive(Set<Integer> set) {
		Set<Set<Integer>> subsets = new HashSet<Set<Integer>>();
		
		subsets.add(new HashSet<Integer>());
		
		for (int i=0; i < set.size(); ++i){
			Set<Set<Integer>> temp = new HashSet<Set<Integer>>();
			for (Set<Integer> subset: subsets){
				for (Integer elem : set){
					Set<Integer> newSet = new HashSet<Integer>();
					newSet.addAll(subset);
					newSet.add(elem);
					temp.add(newSet);
				}
			}
			subsets.addAll(temp);
		}
		
		return subsets;
	}
}
